#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        //if(n == 1)
            //return 0;
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < n; ++i)
        {
            //cout << i << ":";
            for (int j = 0; j < i; ++j)
            {
                if ((i - j) <= nums[j])
                {
                    dp[i] = min(dp[i], dp[j]);
                    //cout << j << " ";
                }
            }
            dp[i] += 1;
            //cout << dp[i] << endl;
        }

        //for(auto& e : dp) cout << e << " ";

        return dp[n - 1];
    }
};